#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

priority = {
    '\\' : -100,    # 哨兵, 优先级最小

    '(' : -1,       # 除哨兵外: 符号中优先级最小的: 不会引起任何计算, 只作为')'匹配的边界
    ')' : -100,     # 优先级最低(越低越不可能和屁股后的字符相结合), 表明当前字符左边的符号优先级更高, 要先计算
                    # 遇到后, 括号内都要计算, until匹配到opes中的'('

    '+' : 1,
    '-' : 1,
    '*' : 2,        # 优先级越高越可能和屁股后字符相结合.
    '/' : 2,
    # '\\' : 3,
}

def prio_enable_calc(ope_left, ope_right):
    # if ope_left == '(':
    #     return False
    # if ope_right == '(':
    #     return False

    # '('特殊一些, 当'(' 比较时, 位于左边和右边的优先级不同.
    # (位于cmp函数右边时, 优先级很大, 也就是第一次进入时. 位于左边时, 优先级很小)
    # 说白了'('无论在哪不会引起计算, 只用来和')'配对.
    if ope_left == '(' or ope_right == '(':
        return False

    print('left, right', ope_left, ope_right)
    return priority[ope_right] <= priority[ope_left]

def step_forward(opes, result):
    # NOTE: WARNING: 注意不负责放入新符号: 无论是否step, 新符号都要在外面放入.
    # b = nums.pop() ; b = float(b)
    # a = nums.pop() ; a = float(a)
    # b = nums.pop()
    # a = nums.pop()
    # o = opes.pop()
    # new_num = calc_map[o](a, b)
    # nums.append(new_num)
    result.append( opes.pop() )
    # return new_num

def try_more_steps(operator, opes, result):
    if prio_enable_calc(opes[-1], operator):
        step_forward(opes, result)
        return try_more_steps(operator, opes, result)

def remains_forward(opes, result):
    while len(opes) > 1 and opes[-1] != '(':
        # print('remians: nums, opes', nums, opes)
        step_forward(opes, result)

def process_emit_operator(operator, opes, result):
    print('process ', operator, opes)
    if operator == '(':
        # 不append, 上层调用方会append
        return

    if operator != ')':
        # trigger只负责触发'operator'之前的符号
        # 不等于命中概率高, 所以放在前面
        # 触发opes中所有比operator优先级高的操作: 4 - (2-3)*1 + 5/5, 遇到+号时, 先把(4 - -2)结账了, 再放入加号
        try_more_steps(operator, opes, result)
    # else:
    #     print('trigger )')
    #     remains_forward(nums, opes)

    return

def infix_2_postfix(expression):
    opes = ["\\"]
    result = []

    idx = 0
    while idx < len(expression):
        ele = expression[idx]

        # 忽略空格
        if ele == " ":
            pass
            # continue

        # elif ele == '(':
        #     opes.append(ele)
        #     # continue

        # 处理计算符号
        elif ele in priority:
            operator = ele
            process_emit_operator(operator, opes, result)
            if operator != ')':
                # '(' 要放入, ')' 不放入
                opes.append(operator)        # 这里无论是否触发之前的计算, 新符号都要放入
            # continue

        # todo1 只支持个位数, 增加到10位数: 步步为营, 先处理最简单的问题.
        # todo2 只支持int, 要支持浮点数
        # 处理数字
        else:
            result.append(ele)
            # ele = parse_int(expression, idx)
            # if ele == "":
            #     raise Exception("['%s'] is invalid character in expression " % expression[idx])

            # nums.append(float(ele))
            # if type(expression) == str:
            #     # 如果是list, 不用往前一步
            #     idx += len(ele) - 1

        idx += 1

        # print('input, nums, opes ', ele, nums, opes)

    print(opes)
    remains_forward(opes, result)
    print('ret', result)
    return result
    # pass

def main():
    print("start main")
    # 在线验证网站, 在线转换:
    # http://scanftree.com/Data_Structure/prefix-postfix-infix-online-converter
    # https://www.mathblog.dk/tools/infix-postfix-converter/
    ret = infix_2_postfix("1+2*3+4")
    ret = infix_2_postfix("1 + 2 * 3 + 4 * 8 * 9 + 10 + 11 + 12")

if __name__ == "__main__":
    main()
